In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic), is a square matrix of nonnegative real numbers, each of whose rows and columns sums to 1. Thus, a doubly stochastic matrix is both left stochastic and right stochastic.[1]
Such a transition matrix is necessarily a square matrix: if every row sums to one then the sum of all entries in the matrix must be equal to the number of rows, and since the same holds for columns, the number of rows and columns must be equal. The class of n × n doubly stochastic matrices is a convex polytope in RN (where N = n2), known as the Birkhoff polytope, Bn. Its dimension is (n − 1)2, since the row and column sums being equal to 1 imposes 2n − 1 linear constraints (not 2n, because if the total of all n columns is n, the same must be true of the total of all n rows).
The principal fact about doubly stochastic matrices is the Birkhoff–von Neumann theorem. This states that the set Bn of doubly stochastic matrices of order n is the convex hull of the set of permutation matrices (of order n), and furthermore that the vertices (extreme points) of Bn are precisely the permutation matrices.
Sinkhorn's theorem states that any matrix with strictly positive entries can be made doubly stochastic by pre- and post-multiplication by diagonal matrices.
For n = 2, all bistochastic matrices are unistochastic and orthostochastic, but for larger n it is not the case.